class Solution:
    def stoneGameII(self, piles: list) -> int:
        def play(preSum, index, M, cache):
            if len(preSum) - index <= 2 * M:
                return preSum[index]
            if (index, M) in cache:
                return cache[(index, M)]
            res = 0
            for x in range(1, 2 * M + 1):
                take = preSum[index] - preSum[index + x]
                res = max(res, take + preSum[index + x] -
                          play(preSum, index + x, max(x, M), cache))
            cache[(index, M)] = res
            return res

        for i in range(len(piles) - 2, -1, -1):
            piles[i] += piles[i + 1]
        return play(piles, 0, 1, {})
